1556. Сравнение с шаблоном

 

Строка file содержит имя файла. Его необходимо преобразовать в строку pattern, которая может содержать символы-джокеры ‘?’ (один любой символ). Необходимо найти наименьшее количество операций вставки, удаления или замены символа, выполнение которых преобразовывают file в pattern.

 

Вход. Каждая строка содержит два слова file и pattern, длины каждого из которых не больше 50. Каждый символ в file является буквой нижнего регистра ('a' - 'z'). Каждый символ в pattern является буквой нижнего регистра ('a' - 'z') или '?'.

 

Выход. Для каждой входной пары слов в отдельной строке вывести наименьшее количество преобразований, при помощи которых из file можно получить pattern.

 

Пример входа

Пример выхода

abcd bcd

aaaabbb aa????b

asdjkhajksdhajksdh asdjkhasdjk?

niceone ieo?e

1

0

6

2

 

 

РЕШЕНИЕ

динамическое программирование

 

Анализ алгоритма

Пусть f[i][j] содержит наименьшее количество преобразований, которые переводят file[1..i] в pattern[1..j]. Нулевым индексам массива f соответствуют пустые строки. Например f[0][0]  = 0 соответствует тому, что для преобразования пустой строки в пустую требуется 0 операций. f[0][j] будет хранить наименьшее количество операций, переводящих пустую строку (“”) в pattern[1..j]. Соответственно f[i][0] будет хранить наименьшее количество операций, переводящих file[1..i] в пустую строку (“”). Очевидно, что f[0][j] = j, f[i][0] = i.

Занесем во все остальные ячейки массива f значение +µ. Рассмотрим, как вычислить значение f[i][j] по известным f[i1][j1], 0 £ i1 < i, 0 £ j1 < j:

· если file[i] = pattern[j] или pattern[j] = '?', то f[i][j] = f[i – 1][j – 1];

· если i - ый символ file и j - ый символ pattern не совпадают, то возможно одно из трех преобразований. Причем производить следует то преобразование, после выполнения которого f[i][j] будет наименьшим, а именно:

· если file[i] заменить на pattern[j], то f[i][j] = f[i – 1][j – 1] + 1;

· если символ file[i] удалить, то f[i][j] = f[i – 1][j] + 1;

· если символ pattern[j] вставить, то f[i][j] = f[i][j – 1] + 1;

Объединив приведенные условия, получим:

f[i][j] = min( min( 1 + f[i – 1][j], 1 + f[i][j – 1]),

(!((file[i] = = pattern[j]) || (pattern[j] = = ‘?’))) + f[i – 1][j – 1]),

f[0][0] = 0.

 

Пример

Построим матрицу f для первого теста

 

 

 

b

c

d

 

i / j

0

1

2

3

 

0

0

1

2

3

a

1

1

1

2

3

b

2

2

1

2

3

c

3

3

2

1

2

d

4

4

3

2

1

 

Реализация алгоритма

Объявим необходимые массивы и переменные.

 

#define MAX 55

int f[MAX][MAX];

char file[MAX], pattern[MAX];

 

Функция minimalChanges возвращает наименьшее количество преобразований, которые переводят file в pattern.

 

int minimalChanges(string file, string pattern)

{

  int i, j;

  memset(f,63,sizeof(f));

 

Устанавливаем f[i][0] = i и f[0][j] = j.

 

  for(i = 0; i < file.size(); i++) f[i][0] = i;

  for(j = 1; j < pattern.size(); j++) f[0][j] = j;

 

Заполняем ячейки f[i][j] согласно соотношениям, приведенным в анализе задачи.

 

  for(i = 1; i < file.size(); i++)

    for(j = 1; j < pattern.size(); j++)

      f[i][j] = min(min(1+f[i-1][j],1 + f[i][j-1]),

                (!((file[i] == pattern[j]) || (pattern[j] == '?'))) +

                f[i-1][j-1]);

  return f[file.size()-1][pattern.size()-1];

}

 

Основной цикл программы. Входные слова зановим в массивы file и pattern, начиная с первой (а не нулевой) позиции.

 

while(scanf("%s %s\n",&file[1],&pattern[1]) == 2)

{

  file[0] = pattern[0] = ' ';

  res = minimalChanges(file,pattern);

  printf("%d\n",res);

}